% \newpage
\section{Kolorowanie ścian}
  Zdefiniujmy na początek mapę.
  \begin{Def}
	\textit{Mapą} nazywamy 3-spójny graf planarny.
  \end{Def}
  Jak się za chwilę przekonamy, rozpatrywanie innych grafów niż mapy przy tym zagadnieniu nie ma większego sensu. Wprowadźmy teraz pojęcie grafu geometrycznie dualnego.
  \begin{Def}
	Jeżeli mamy dany planarny graf $G=(V,E)$ wraz z jego reprezentacją na płaszczyźnie (bez przecięć), możemy skonstruować dla niego graf \textit{geometrycznie dualny} $G^*=(V^*,E^*)$. W grafie tym każdej ścianie odpowiada dokładnie jeden wierzchołek z $V$, każdemu wierzchołkowi z $V^*$ odpowiada dokładnie jedna ściana z $G$ oraz każdej krawędzi z $E^*$ odpowiada dokładnie jedna krawędź z $E$.
  \end{Def}
  Tak więc, graf taki możemy skonstruować rysując na każdej ścianie grafu $G$ (także zewnętrznej) wierzchołek, a następnie przez każdą krawędź $e \in E$ poprowadzić krawędź $e^*$ łączącą wierzchołki odpowiadające ścianom, które krawędź $e$ rozdziela. 
  \begin{Prz}
	Graf $G$ reprezentowany jest przez wierzchołki okrągłe oraz ciągłe krawędzie natomiast graf geometrycznie dualny $G^*$ przez wierzchołki kwadratowe i przerywane krawędzie.
	\begin{figure}[!h]\centering\begin{tikzpicture}
		\clip (-1.5,-0.5) rectangle (6.2,5.1);
		\tikzstyle{Vnorm}=[inner sep=0, minimum size=6, draw=black,circle]
		\tikzstyle{Enorm}=[thick]
		\tikzstyle{Vdual}=[inner sep=0, minimum size=6, draw=gray!70, fill=lightgray!70,rectangle]
		\tikzstyle{Edual}=[draw=gray, densely dashed]

		\node(a)[Vnorm] at (0.5,0.5) {};
		\node(b)[Vnorm] at (5,0) {}
			edge[Enorm, bend left] (a);
		\node(c)[Vnorm] at (2,1) {}
			edge[Enorm] (a)
			edge[Enorm] (b);
		\node(d)[Vnorm] at (4,2) {}
			edge[Enorm] (b)
			edge[Enorm, bend right] (c);
		\node(e)[Vnorm] at (2,4) {}
			edge[Enorm, bend right] (a)
			edge[Enorm] (d);
		\node(f)[Vnorm] at (5,4) {}
			edge[Enorm, bend left] (b)
			edge[Enorm] (d)
			edge[Enorm, bend right] (e);

		\node(A)[Vdual] at (2.4, 0) {};
		\node(B)[Vdual] at (3.5,1.2) {}
			edge[Edual] (A);
		\node(C)[Vdual] at (1.5,2.3) {}
			edge[Edual, bend right] (A)
			edge[Edual] (B);
		\node(D)[Vdual] at (3.6,3.5) {}
			edge[Edual] (C);
		\node(E)[Vdual] at (4.9, 2) {}
			edge[Edual] (D)
			edge[Edual] (B);
		\node(F)[Vdual] at(-0.5, 2) {}
			edge[Edual, bend right=100] (A)
			edge[Edual] (C)
			edge[Edual, bend left=90] (D)
			edge[Edual, controls=(130:8) and (30:12), in=0] (E);
	\end{tikzpicture}\caption{}\end{figure}
  \end{Prz}
  Po chwili obserwacji oraz przemyśleniu definicji łatwo zauważyć, że $(G^*)^*$ jest izomorficzny z $G$, stąd też nazwa -- dualny. Co za tym idzie wszystkie twierdzenia dotyczące kolorowania wierzchołków grafów planarnych można przeformułować na równoważne twierdzenia o kolorowaniu ścian i na odwrót.

  \begin{Def}
	\textit{Graf eulerowski} jest to graf, którego cały zbiór krawędzi -- używając każdej krawędzi dokładnie raz -- można ustawić w trasę zaczynającą i kończącą się w tym samym wierzchołku.
  \end{Def} 
  Warunkiem koniecznym i wystarczającym na to, żeby graf był eulerowskim jest to, aby jego wierzchołek był parzystego stopnia (\cite{wprowadzeniedoteorii} s.48).

  \begin{Tw}\label{walls:euler2col}
	Graf planarny $G$ jest 2-kolorowalny(f) $\iff$ gdy $G$ jest grafem eulerowskim.
  \end{Tw}
  \begin{Dw}
	To że graf $G$ jest 2-kolorowalny(f) oznacza, że graf $G^*$ geometrycznie dualny do niego jest dwudzielny (2-kolorowalny wierzchołkowo). Wiadomo o grafach dwudzielnych, że każdy zawarty w nich cykl jest parzystej długości (\cite{wprowadzeniedoteorii} s. 42). Krawędzie ograniczające ściany tworzą cykle, a więc wiemy, że w $G^*$ każda ściana ograniczana jest parzystą liczbą krawędzi. Stąd też wnioskujemy, że w grafie $G$ każdy wierzchołek jest stopnia parzystego, co oznacza, że $G$ jest grafem eulerowskim.
	
	W drugą stronę wykorzystamy fakt, że grafy eulerowskie można rozdzielić na zbiór cykli nie posiadajcych wspólnych krawędzi (\cite{wprowadzeniedoteorii} s. 49). Naruszymy tutaj nieco definicję cyklu, aby przedstawić dowód w prostszy sposób. Przyjmijmy że w cyklu wierzchołki mogą występować wielokrotnie - w tym wypadku będzie to łaczenie cykli posiadających dokładnie jeden wspólny wierzchołek. Możemy wtedy podzielić graf $G$ na cykle w taki sposób, aby każdy z nich ograniczał dokładnie jedną ścianę. Żadna para cykli nie ma wspólnej krawędzi, więc można pokolorować je jednym kolorem, z kolei pozostałe ściany także nie mogą ze sobą sąsiadować ponieważ podział nie pozostawiał żadnych krawędzi wolnych. Mamy więc podział zbioru ścian na dwa rozłączne podzbiory, czyli możliwe jest pokolorowanie grafu dwoma barwami.
  \end{Dw}

  Ciekawym przypadkiem są mapy kubiczne.
  \begin{Def}
	Graf $G=(V,E)$ nazywamy mapą kubiczną, gdy każdy z jego wierzchołków $v\in V$ jest stopnia $deg(v)=3$.
  \end{Def}
  \begin{Tw}
	Mapy kubiczne są 3-kolorowalne $\iff$ gdy każda z jej ścian ograniczona jest parzystą liczbą krawędzi.
  \end{Tw}
  \begin{Dw}
	Niech $G=(V,E)$ będzie mapą kubiczną, a $G^*$ jej grafem geometrycznie dualnym. Rozpatrzmy pojedyńczą ścianę. Ponieważ każdy wierzchołek $v \in V$ jest stopnia $deg(v)=3$ możemy zauważyć, że każde dwie ściany, mające krawędzie wspólne z rozpatrywaną oraz kończące się w jednym wierzchołku, muszą ze sobą sąsiadować. Stąd wierzchołki, odpowiadające ścianom okalającym rozpatrywaną, tworzą w grafie dualnym $G^*$ cykl. Skoro graf ma być 3-kolorowalny(f), to wszystkie ściany mające wspólną ścianę sąsiednią, mogą być kolorowane jedynie dwoma barwami. Jak wiemy cykle są 2-kolorowalne tylko, gdy są parzystej długości, więc każda ściana musi mieć parzystą liczbę sąsiadów.

	Jeżeli wiemy że każda ze ścian w grafie $G$ jest ograniczona parzystą liczbą krawędzi, a każdy wierzchołek ma stopień $deg(v)=3$, to graf $G^*$ geometrycznie dualny do niego, będzie miał każdy wierzchołek stopnia parzystego oraz każdą ścianę ograniczoną trzema krawędziami. Jak mówi twierdzenie \ref{walls:euler2col}, grafy eulerowskie (o wszystkich wierzchołkach stopnia parzystego) są 2-kolorowalne(f). Wykorzystując jeszcze fakt, że każda ściana jest trójkątem możemy utworzyć 3-kolorowanie wierzchołków grafu $G^*$ (czyli ścian w $G$). Przyjmijmy że ściany w $G^*$ mają kolory $a$ i $b$. Kolorując teraz wierzchołki jednej ze ścian koloru $a$, barwami 1,2 i 3, w kolejności zgodnej z ruchem wskazówek zegara a ściany sąsiednie (koloru $b$) w kolejności odwrotnej i postępując tak aż wszystkie wierzchołki będa pokolorowane uzyskujemy żądane 3-kolorowanie(f) grafu $G$.
  \end{Dw}

  \begin{Tw}
	Dowód twierdzenia o czterech barwach dla map kubicznych jest równoważny do dowodu tego twierdzenia dla wszystkich map.
  \end{Tw}
  \begin{Dw}
	Pokażemy że każdą mapę można przekształcić w mapę kubiczną, którą po kolorowaniu można przekształcić z powrotem w zwykłą mapę, bez naruszenia kolorowania. Mapę zwykłą od kubicznej różni to że może ona mieć wierzchołki stopnia większego niż 3. Takich wierzchołków można się chwilowo 'pozbyć' poprzez tak zwane ``naklejenie łatki'', czyli tworzymy z wierzchołka ścianę tak jak na rysunku poniżej.
	\begin{figure}[!h]\centering\begin{tikzpicture}[scale=1.5]
	  \tikzstyle{visible}=[draw, circle, inner sep=0, minimum size=7]

	  \node(v)[visible] at(0,0) {};
	  \foreach \i in {1,...,4}
		  \node at({(90*\i+45)}:1) {} edge(v);

	  \draw[stealth-stealth, gray, snake=snake, segment length=4, segment amplitude=1, line around snake=2.7] (1,0) -- (2,0);

	  \begin{scope}[shift={(3,0)}]
		  \node(w1)[visible] at(0.3,0.3) {};
		  \node(w2)[visible] at(-0.3,0.3) {} edge[bend left](w1);
		  \node(w3)[visible] at(-0.3,-0.3) {} edge[bend left](w2);
		  \node(w4)[visible] at(0.3,-0.3) {} edge[bend left](w3) edge[bend right](w1);
		  \foreach \i in {1,...,4}
			  \node at({(90*\i-45)}:1) {} edge(w\i);
	  \end{scope}
	\end{tikzpicture}\caption{}\end{figure}
	\newline Po wyeliminowaniu tym sposobem wszystkich wierzchołków o stopniu większym od 3, otrzymujemy mapę kubiczną. Następnie po wykonaniu kolorowania tej mapy można wrócić do jej pierwotnej postaci, usuwając naklejone łatki, co jak widać na rysunku, nie zaburzy w żaden sposób kolorowania. 
  \end{Dw}
